package com.wangjie.stackandqueue;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author jieshao
 * @date 2022/5/13 10:43
 *
 * 单调栈解决 next greater element 问题
 *
 * 给定一个数组 nums，请你返回一个等长的结果数组，结果数组中对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1
 */
public class Test06 {
    public static void main(String[] args) {
        int[] arr = {2, 1, 2, 4, 3};
        int[] res = nextGreaterElement(arr);
        System.out.println(Arrays.toString(res));
    }

    /**
     * 倒序遍历 nums，并用单调栈维护当前位置右边的更大的元素列表，从栈底到栈顶的元素是单调递减的。每次我们移动到数组中一个新的位置 i，就将当前
     * 单调栈中所有小于 nums[i] 的元素弹出单调栈，当前位置右边的第一个更大的元素即为栈顶元素，如果栈为空则说明当前位置右边没有更大的元素。随后
     * 我们将位置 i 的元素入栈。
     *
     * @param nums
     * @return
     */
    public static int[] nextGreaterElement(int[] nums) {
        int[] res = new int[nums.length];
        Stack<Integer> s = new Stack<>();
        // 倒着往栈里放
        for (int i = nums.length - 1; i >= 0; i--) {
            // 判定个子高矮
            while (!s.empty() && s.peek() <= nums[i]) {
                // 矮个起开，反正也被挡着了
                s.pop();
            }
            // nums[i] 身后的 next great number
            res[i] = s.empty() ? -1 : s.peek();
            s.push(nums[i]);
        }
        return res;
    }
}